package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 22:56 2020/4/1
 * @Description  数组中出现次数超过一半的数字
 */

public class FaceTest_39 {

    // 使用摩尔投票法，到最后票数为正的一定是众数  也可以采用排序法，众数一定会在中间位置
    // 每次假设当前第一个是众数，如果是众数就vote+1，不过不是就-1，如果vote==0就重新选择
    public int majorityElement(int[] nums) {

        int vote = 0;
        // 众数（题目一直一定会有众数，这里可以随便设置值）
        int ans = 0;

        for (int num : nums) {
            if (vote == 0){
                ans = num;
                vote++;
            }else {
                if (ans == num) vote ++;
                else vote--;
            }
        }
        return ans;
    }
}
